//
//  tree.hpp
//  408数据结构
//
//  Created by Cai Yuanhao on 2022/3/28.
//

#ifndef tree_hpp
#define tree_hpp

#include <stdio.h>

#endif /* tree_hpp */
#include <stdlib.h>

typedef char BiElemType;
typedef struct BiTNode{
    BiElemType c;//c就是书籍上的data
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;

typedef struct tag{
    BiTree p;//树的某一个结点的地址值
    struct tag *pnext;
}tag_t,*ptag_t;

//栈的相关数据结构
#define MaxSize 50
typedef BiTree ElemType;
typedef struct{
    ElemType data[MaxSize];
    int top;
}SqStack;
void InitStack(SqStack &S);
bool StackEmpty(SqStack &S);
bool Push(SqStack &S,ElemType x);
bool Pop(SqStack &S,ElemType &x);
bool GetTop(SqStack &S,ElemType &x);
//队列的相关数据结构
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{
    LinkNode *front,*rear;
}LinkQueue;
void InitQueue(LinkQueue &Q);
bool IsEmpty(LinkQueue Q);
void EnQueue(LinkQueue &Q,ElemType x);
bool DeQueue(LinkQueue &Q,ElemType &x);

void InitQueue(LinkQueue &Q)
{
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

bool IsEmpty(LinkQueue Q)
{
    if(Q.front==Q.rear)
        return true;
    else
        return false;
}

void EnQueue(LinkQueue &Q,ElemType x)
{
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}

bool DeQueue(LinkQueue &Q,ElemType &x)
{
    if(Q.front==Q.rear) return false;
    LinkNode *p=Q.front->next;//头结点什么都没存，所以头结点的下一个节点才有数据
    x=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)
        Q.rear=Q.front;
    free(p);
    return true;
}

void InitStack(SqStack &S)
{
    S.top=-1;
}

bool StackEmpty(SqStack &S)
{
    if(S.top==-1)
        return true;
    else
        return false;
}
//入栈
bool Push(SqStack &S,ElemType x)
{
    if(S.top==MaxSize-1)
    {
        return false;
    }
    S.data[++S.top]=x;
    return true;
}
//出栈
bool Pop(SqStack &S,ElemType &x)
{
    if(-1==S.top)
        return false;
    x=S.data[S.top--];
    return true;
}
//读取栈顶元素
bool GetTop(SqStack &S,ElemType &x)
{
    if(-1==S.top)
        return false;
    x=S.data[S.top];
    return true;
}
